【剑指offer】【Java】数组中的逆序对

题目

链接：https://www.nowcoder.com/questionTerminal/96bd6684e04a44eb80e6a68efc0ec6c5
来源：牛客网

在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P%1000000007

代码

注意点：

• 归并排序：Java不能切片，所以用start,end，mid控制数组内切片长度
• Java

public class Solution {
    private int count;
    public int InversePairs(int [] array) {
        count = 0;
        if(array != null){
            mergeSort(array, 0, array.length - 1);
        }
        return count;
    }

    private void mergeSort(int[] a, int start, int end){
        if(start >= end)
            return;
        int mid = start + (end - start) / 2;
        mergeSort(a, start, mid);
        mergeSort(a, mid+1, end);
        merge(a,start,mid,end);
    }

    private void merge(int[] a, int start, int mid, int end){
        int[] temp = new int[end-start+1];
        int i = start, j = mid + 1, k = 0;
        while (i <= mid && j <= end) {
            if (a[i] <= a[j])
                temp[k++] = a[i++];
            else {
                temp[k++] = a[j++];
                // ai大于aj，由于归并，所以相反的必定是和所有前面的数字，所以是mid到最左边i中间的数的个数
                count = (count + mid - i + 1) % 1000000007;
            }
        }

        while (i <= mid)
            temp[k++] = a[i++];
        while (j <= end)
            temp[k++] = a[j++];
        for(k=0;k<temp.length;k++){ //将临时数组的数字写回a数组！
            a[start+k] = temp[k];
        }
    }
}